#include <bits/stdc++.h>
using namespace std;

/*
3508. 设计路由器
已解答
中等
相关标签
premium lock icon
相关企业
提示
请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：

source：生成该数据包的机器的唯一标识符。
destination：目标机器的唯一标识符。
timestamp：该数据包到达路由器的时间戳。
实现 Router 类：

Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。

memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。
如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。
bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。

如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。
int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。

从存储中移除该数据包。
以数组 [source, destination, timestamp] 的形式返回该数据包。
如果没有数据包可以转发，则返回空数组。
int getCount(int destination, int startTime, int endTime)：

返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。
注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。

 

示例 1：

输入：
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

输出：
[null, true, true, false, true, true, [2, 5, 90], true, 1]

解释：

Router router = new Router(3); // 初始化路由器，内存限制为 3。
router.addPacket(1, 4, 90); // 数据包被添加，返回 True。
router.addPacket(2, 5, 90); // 数据包被添加，返回 True。
router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。
router.addPacket(3, 5, 95); // 数据包被添加，返回 True。
router.addPacket(4, 5, 105); // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
router.forwardPacket(); // 转发数据包 [2, 5, 90] 并将其从路由器中移除。
router.addPacket(5, 2, 110); // 数据包被添加，返回 True。
router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。
示例 2：

输入：
["Router", "addPacket", "forwardPacket", "forwardPacket"]
[[2], [7, 4, 90], [], []]

输出：
[null, true, [7, 4, 90], []]

解释：

Router router = new Router(2); // 初始化路由器，内存限制为 2。
router.addPacket(7, 4, 90); // 返回 True。
router.forwardPacket(); // 返回 [7, 4, 90]。
router.forwardPacket(); // 没有数据包可以转发，返回 []。
 

提示：

2 <= memoryLimit <= 105
1 <= source, destination <= 2 * 105
1 <= timestamp <= 109
1 <= startTime <= endTime <= 109
addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 105。
对于 addPacket 的查询，timestamp 按递增顺序给出。
*/

// 法一
class Router {
public:
    int memLimit = 0;
    int length = 0;
    set<tuple<int, int, int>> isExist;
    unordered_map<int, deque<int>> sameDestQue;
    deque<tuple<int, int, int>> que;

    Router(int memoryLimit) { memLimit = memoryLimit; }

    bool addPacket(int source, int destination, int timestamp) {
        tuple<int, int, int> packet =
            make_tuple(source, destination, timestamp);
        if (isExist.contains(packet)) {
            return false;
        }
        if (length == memLimit) {
            forwardPacket();
        }
        length++;
        que.push_back(packet);
        sameDestQue[destination].push_back(timestamp);
        isExist.insert(packet);
        return true;
    }

    vector<int> forwardPacket() {
        vector<int> data;
        if (!que.empty()) {
            tuple<int, int, int> packet = que.front();
            que.pop_front();
            data = vector<int>{get<0>(packet), get<1>(packet), get<2>(packet)};
            isExist.erase(packet);
            sameDestQue[data[1]].pop_front();
            length--;    
        }
        return data;
    }

    int getCount(int destination, int startTime, int endTime) {
        auto pos1 = lower_bound(sameDestQue[destination].begin(),
                                sameDestQue[destination].end(), startTime);
        auto pos2 = upper_bound(sameDestQue[destination].begin(),
                                sameDestQue[destination].end(), endTime);
        return pos2 - pos1;
    }
};

// 法二 通用模板类 参考boost
// 通用tuple哈希结构体：支持任意类型、任意长度的tuple生成哈希值（模板元编程实现）
struct TupleHash {
    // 哈希组合函数：将单个值的哈希合并到种子中，减少碰撞概率（参考boost实现）
    template<typename T>
    static void hash_combine(size_t& seed, const T& v) {
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    // 递归哈希tuple元素：从索引0开始，依次处理每个元素
    template<typename Tuple, size_t Index = 0>
    static void hash_tuple(size_t& seed, const Tuple& t) {
        if constexpr(Index < tuple_size_v<Tuple>) {  // 编译期判断是否处理完所有元素
            hash_combine(seed, get<Index>(t));       // 合并当前元素的哈希
            hash_tuple<Tuple, Index + 1>(seed, t);   // 递归处理下一个元素
        }
    }

    // 为任意tuple生成哈希值：入口函数
    template<typename... Ts>
    size_t operator()(const tuple<Ts...>& t) const {
        size_t seed = 0;
        hash_tuple(seed, t);  // 递归处理tuple所有元素
        return seed;
    }
};

class Router {
    int memory_limit;  // 路由器最大可存储的数据包数量
    queue<tuple<int, int, int>> packet_q;  // FIFO队列：存储数据包（source, dest, timestamp），保证转发顺序
    // 无序集合：基于通用TupleHash，快速检测重复数据包（三要素完全相同视为重复）
    unordered_set<tuple<int, int, int>, TupleHash> packet_set;
    // 目标地址映射：key=目标地址，value={时间戳列表, 有效起始索引head}
    // 核心优化：用head标记已转发的时间戳（避免vector.erase的O(n)开销），有效数据从head开始
    unordered_map<int, pair<vector<int>, int>> dest_to_timestamps;

public:
    // 构造函数：初始化内存限制
    Router(int memoryLimit) : memory_limit(memoryLimit) {}
    
    // 添加数据包：返回是否成功（非重复）
    bool addPacket(int source, int destination, int timestamp) {
        auto packet = make_tuple(source, destination, timestamp);
        // 检测重复：insert返回的pair中second为false表示已存在该数据包
        if (!packet_set.insert(packet).second) {
            return false;
        }
        // 内存已满：转发最旧的数据包（FIFO）腾出空间
        if (packet_q.size() == memory_limit) {
            forwardPacket();
        }
        packet_q.push(packet);  // 新数据包入队
        // 记录时间戳到目标地址的列表（因addPacket的timestamp递增，列表天然有序）
        dest_to_timestamps[destination].first.push_back(timestamp);
        return true;
    }
    
    // 转发最旧数据包：返回数据包信息并从存储中移除
    vector<int> forwardPacket() {
        if (packet_q.empty()) {
            return {};  // 无数据包可转发
        }
        auto packet = packet_q.front();  // 取队首（最旧的数据包）
        packet_q.pop();                  // 出队
        packet_set.erase(packet);        // 从去重集合中移除
        
        auto [source, destination, timestamp] = packet;
        // 递增head标记该目标地址下的已转发时间戳（有效数据从head开始）
        dest_to_timestamps[destination].second++;
        
        return {source, destination, timestamp};
    }
    
    // 统计目标地址在[startTime, endTime]内的数据包数量
    int getCount(int destination, int startTime, int endTime) {
        // 获取目标地址的时间戳列表和有效起始索引head
        auto& [timestamps, head] = dest_to_timestamps[destination];
        // 有效时间戳范围：[head, timestamps.size())（跳过已转发的部分）
        // 二分查找范围边界：left是第一个>=startTime的位置，right是第一个>endTime的位置
        auto left = ranges::lower_bound(timestamps.begin() + head, timestamps.end(), startTime);
        auto right = ranges::upper_bound(timestamps.begin() + head, timestamps.end(), endTime);
        return right - left;  // 范围内元素数量即为结果
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

// 法三
// 自定义哈希结构体：为tuple<int, int, int>生成哈希值，减少碰撞
struct TupleHash {
    // 哈希组合函数：参考boost实现，将多个值的哈希合并为一个
    template<typename T>
    static void hash_combine(size_t& seed, const T& v) {
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    }

    // 为(source, destination, timestamp) tuple生成哈希值
    size_t operator()(const tuple<int, int, int>& t) const {
        auto& [a, b, c] = t;
        size_t seed = 0;
        hash_combine(seed, a);  // 合并source哈希
        hash_combine(seed, b);  // 合并destination哈希
        hash_combine(seed, c);  // 合并timestamp哈希
        return seed;
    }
};

class Router {
    int memory_limit;  // 路由器最大存储数据包数量
    queue<tuple<int, int, int>> packet_q;  // FIFO队列：存储数据包，保证转发顺序
    // 无序集合：存储数据包tuple，O(1)检测重复（source+destination+timestamp唯一）
    unordered_set<tuple<int, int, int>, TupleHash> packet_set;
    // 目标地址映射：key=destination，value={时间戳列表, 有效起始索引head}
    // head用于标记已转发的时间戳（避免vector频繁erase，优化性能）
    unordered_map<int, pair<vector<int>, int>> dest_to_timestamps;

public:
    // 初始化：设置内存限制
    Router(int memoryLimit) : memory_limit(memoryLimit) {}

    // 添加数据包：返回是否成功（非重复）
    bool addPacket(int source, int destination, int timestamp) {
        auto packet = make_tuple(source, destination, timestamp);
        // 检测重复：insert返回pair，second为false表示已存在
        if (!packet_set.insert(packet).second) {
            return false;
        }
        // 内存满：转发最旧数据包（FIFO）腾出空间
        if (packet_q.size() == memory_limit) {
            forwardPacket();
        }
        packet_q.push(packet);  // 入队
        // 记录时间戳到目标地址的列表（后续用于范围查询）
        dest_to_timestamps[destination].first.push_back(timestamp);
        return true;
    }

    // 转发最旧数据包：返回数据包信息，从存储中移除
    vector<int> forwardPacket() {
        if (packet_q.empty()) {
            return {};  // 无数据包可转发
        }
        auto packet = packet_q.front();  // 取队首（最旧）
        packet_q.pop();                  // 出队
        packet_set.erase(packet);        // 从集合移除
        
        auto [source, destination, timestamp] = packet;
        // 递增head标记该时间戳已无效（避免vector.erase的O(n)开销）
        dest_to_timestamps[destination].second++;
        
        return {source, destination, timestamp};
    }

    // 统计目标地址在[startTime, endTime]内的数据包数量
    int getCount(int destination, int startTime, int endTime) {
        // 获取目标地址的时间戳列表和有效起始索引head
        auto& [timestamps, head] = dest_to_timestamps[destination];
        // 有效时间戳范围：[head, timestamps.size())（跳过已转发的）
        auto left = ranges::lower_bound(timestamps.begin() + head, timestamps.end(), startTime);
        auto right = ranges::upper_bound(timestamps.begin() + head, timestamps.end(), endTime);
        return right - left;  // 范围内元素数量
    }
};

// 法四  最易于理解
// 自定义哈希函数：用于unordered_set存储tuple<source, dest, timestamp>
struct TupleHash {
    template <typename T1, typename T2, typename T3>
    size_t operator()(const tuple<T1, T2, T3>& t) const {
        auto h1 = hash<T1>{}(get<0>(t));
        auto h2 = hash<T2>{}(get<1>(t));
        auto h3 = hash<T3>{}(get<2>(t));
        // 组合哈希值，减少碰撞概率
        return h1 ^ (h2 << 16) ^ (h3 << 32);
    }
};

class Router {
private:
    // 数据包结构体
    struct Packet {
        int source;
        int dest;
        int ts; // timestamp
        Packet(int s, int d, int t) : source(s), dest(d), ts(t) {}
    };

    int memoryLimit;                // 路由器内存限制（最大数据包数量）
    queue<Packet> pktQueue;         // FIFO队列：维护数据包转发顺序
    unordered_set<tuple<int, int, int>, TupleHash> existPkts; // 去重集合：source+dest+ts唯一
    unordered_map<int, vector<int>> destTsVec; // 按目标分组的时间戳列表：dest→[ts1, ts2,...]（天然有序，因addPacket的ts递增）
    unordered_map<int, int> tsToDest;          // 时间戳→目标地址：快速定位ts所属的dest

public:
    // init
    Router(int memoryLimit) : memoryLimit(memoryLimit) {}
    
    // 去重set  内存控制  
    bool addPacket(int source, int destination, int timestamp) {
        // only key
        auto pktKey = make_tuple(source, destination, timestamp);
        if (existPkts.count(pktKey))    return false;   // 重复，添加失败

        // 内存超过限制  旧的数据包不要了 FIFO 去腾出空间
        while (pktQueue.size() >= memoryLimit) {
            Packet old = pktQueue.front();
            pktQueue.pop();

            // old 的record 删了
            existPkts.erase(make_tuple(old.source, old.dest, old.ts));
            // ts  的list里面都要删了 ts递增，旧数据包的ts是列表首元素
            auto& tsVect = destTsVec[old.dest];
            if (!tsVect.empty() && tsVect[0] == old.ts) {
                tsVect.erase(tsVect.begin());
                if (tsVect.empty())     destTsVec.erase(old.dest);
            }
            tsToDest.erase(old.ts);
        }

        // 新增数据包：同步插入所有数据结构
        Packet newPkt(source, destination, timestamp);
        pktQueue.push(newPkt);
        existPkts.insert(pktKey);

        // timestamp 天然有排序  直接尾插
        destTsVec[destination].push_back(timestamp);
        tsToDest[timestamp] = destination;

        return true;
    }
    
    // 转发 FIFO顺序，移除并返回最旧数据包
    vector<int> forwardPacket() {
        if (pktQueue.empty())   return {};

        // 取出
        Packet frontPkt = pktQueue.front();
        pktQueue.pop();

        existPkts.erase(make_tuple(frontPkt.source, frontPkt.dest, frontPkt.ts));

        // ts列表中去删除
        auto destIt = destTsVec.find(frontPkt.dest);
        if (destIt != destTsVec.end()) {
            auto& tsVec = destIt->second;
            if (!tsVec.empty() && tsVec[0] == frontPkt.ts) {
                tsVec.erase(tsVec.begin());
                if (tsVec.empty()) {
                    destTsVec.erase(destIt);
                }
            }
        }
        tsToDest.erase(frontPkt.ts);

        // 返回数据包信息
        return {frontPkt.source, frontPkt.dest, frontPkt.ts};
    }
    
    // 目标地址+时间范围内的数据包数量
    int getCount(int destination, int startTime, int endTime) {
        // 目标地址无数据包，直接返回0
        auto destIt = destTsVec.find(destination);
        if (destIt == destTsVec.end())           return 0;

        const auto& tsVec = destIt->second;
        // 二分查找时间范围的左右边界（vector有序，O(log n)）
        // lower_bound：第一个>=startTime的元素
        auto left = lower_bound(tsVec.begin(), tsVec.end(), startTime);
        // upper_bound：第一个>endTime的元素
        auto right = upper_bound(tsVec.begin(), tsVec.end(), endTime);

        // 迭代器差即为数量（vector是随机访问迭代器，O(1)计算）
        return right - left;
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */

// 法五
class Router {
    // 存储目标地址的时间戳信息：key=destination，value={时间戳列表, 有效起始索引s}
    // s标记已转发的时间戳位置，有效数据从s开始（避免vector.erase的O(n)开销）
    unordered_map<int, pair<vector<int>, int>> h;
    // 去重集合：key=source和destination的组合（uint64_t），value=timestamp
    // 用于快速检测(source, destination, timestamp)是否重复
    unordered_map<uint64_t, int> st;
    // 环形队列：存储source和destination的组合（uint64_t），维护数据包的FIFO顺序
    uint64_t* q;
    int full;       // 标记环形队列是否已满
    int head;       // 环形队列头指针（指向最早入队的元素）
    int tail;       // 环形队列尾指针（指向即将入队的位置）
    const int LEN;  // 环形队列长度（内存限制）

public:
    // 构造函数：初始化环形队列及状态变量
    Router(int memoryLimit) : q(new uint64_t[memoryLimit]), full(0), head(0), tail(0), LEN(memoryLimit) {}
    
    // 析构函数：释放环形队列的动态内存
    ~Router() {
        delete[] q;
    }
    
    // 添加数据包：返回是否成功（非重复）
    bool addPacket(int source, int destination, int timestamp) {
        // 组合source和destination为64位key：高32位存destination，低32位存source
        uint64_t key = (uint64_t)destination << 32 | source;
        // 检测重复：若key存在且timestamp相同，返回false
        if (st.contains(key) && st[key] == timestamp) {
            return false;
        }
        // 队列满：转发最旧数据包（FIFO）腾出空间
        if (full) {
            forwardPacket();
        }
        // 新数据包入队（环形队列尾指针位置）
        q[tail] = key;
        // 记录时间戳到目标地址的列表（因timestamp递增，列表天然有序）
        h[destination].first.push_back(timestamp);
        // 更新尾指针（环形队列循环）
        tail = (tail + 1) % LEN;
        // 标记队列是否已满（头指针等于尾指针时）
        full = (head == tail);
        // 更新去重集合：记录key对应的timestamp
        st[key] = timestamp;
        return true;
    }
    
    // 转发最旧数据包：返回数据包信息并从存储中移除
    vector<int> forwardPacket() {
        // 队列为空（头指针等于尾指针且未标记为满）
        if (head == tail && !full) {
            return {};
        }
        // 解析队列头元素：高32位是destination，低32位是source
        int dest = q[head] >> 32;
        int sour = q[head] & UINT32_MAX;
        // 获取当前目标地址的有效时间戳（从有效起始索引s开始）
        int tot = h[dest].first[h[dest].second];
        // 递增有效起始索引s（标记该时间戳已转发）
        h[dest].second += 1;
        // 清除队列满标记
        full = 0;
        // 从去重集合中移除该数据包（验证timestamp匹配）
        auto it = st.find(q[head]);
        if (it != st.end() && tot == it->second) {
            st.erase(it);
        }
        // 更新头指针（环形队列循环）
        head = (head + 1) % LEN;
        return {sour, dest, tot};
    }
    
    // 统计目标地址在[startTime, endTime]内的数据包数量
    int getCount(int destination, int startTime, int endTime) {
        // 目标地址无数据包，返回0
        if (!h.contains(destination)) {
            return 0;
        }
        // 获取时间戳列表和有效起始索引s（跳过已转发的）
        const auto& [nq, s] = h[destination];
        // 二分查找范围边界：有效数据从s开始，计算[startTime, endTime]内的数量
        return upper_bound(nq.begin() + s, nq.end(), endTime) - 
               lower_bound(nq.begin() + s, nq.end(), startTime);
    }
};

/**
 * Your Router object will be instantiated and called as such:
 * Router* obj = new Router(memoryLimit);
 * bool param_1 = obj->addPacket(source,destination,timestamp);
 * vector<int> param_2 = obj->forwardPacket();
 * int param_3 = obj->getCount(destination,startTime,endTime);
 */